#include <iostream>
#include <vector>

// 检查当前状态是否安全
bool IsSafe(const std::vector<bool>& now) {
    // 检查狼会不会吃掉羊
    if ((now[1] == now[2]) && (now[0]!= now[1])) return false;
    // 检查羊会不会吃掉菜
    if ((now[2] == now[3]) && (now[0]!= now[2])) return false;
    return true;
}

// 检查当前状态是否已经出现过
bool isRepeated(const std::vector<bool>& now, const std::vector<int>& dira, int a, int step) {
    for (int i = 0; i < step; i++) {
        if (dira[i] == a) return true;
    }
    return false;
}

// 显示路径
void display(const std::vector<int>& dira) {
    for (int i = 0; i <= 17; i++) {
        std::cout << dira[i] << " ";
    }
    std::cout << std::endl;
}

// 输出路径
void path(const std::vector<int>& dira) {
    int i = 0;
    while (dira[i]!= 0) {
        int diff = dira[i] - dira[i + 1];
        switch (diff) {
            case 8:
            case -8:
                std::cout << "农夫独自过河\n";
                break;
            case 12:
            case -12:
                std::cout << "农夫带狼过河\n";
                break;
            case 10:
            case -10:
                std::cout << "农夫带羊过河\n";
                break;
            case 9:
            case -9:
                std::cout << "农夫带菜过河\n";
                break;
            default:
                std::cout << "未知动作\n";
                break;
        }
        i++;
    }
}

// 回溯法函数
void backtracking(std::vector<bool>& now, std::vector<int>& dira, int step) {
    int a = now[0] * 8 + now[1] * 4 + now[2] * 2 + now[3] * 1;
    // 剪枝
    if (isRepeated(now, dira, a, step) ||!IsSafe(now)) return;
    dira[step] = a;
    if (now[0] == 0 && now[1] == 0 && now[2] == 0 && now[3] == 0) {
        static int count = 0;
        count++;
        std::cout << "过河的第" << count << "的方法\n";
        // display(dira);
        path(dira);
        std::cout << std::endl;
        return;
    }
    // 尝试每种可能的移动方式
    for (int i = 0; i < 4; i++) {
        if (now[i] == now[0]) {  // 物体和农夫在同一侧
            std::vector<bool> temp = now;
            now[i] =!now[i];
            if (i!= 0) now[0] =!now[0];
            backtracking(now, dira, step + 1);
            now = temp;
        }
    }
}

int main() {
    std::vector<bool> now = {true, true, true, true};
    std::vector<int> dira(18, 0);
    backtracking(now, dira, 0);
    return 0;
}